# encoding: utf-8
module OJ
  class Fiber_Tree
    Node = Struct.new(:data, :parent, :childern)
    Data = Struct.new(:fiber, :args, :condition, :alive, :alive_childern, :results)
    attr_reader :current, :leafs

    def initialize
      # root can only be used as parent node
      @root = Node.new
      @leafs = []
      @revive_nodes = []
    end

    def insert_leafs(data_list, parent_ix)
      if parent_ix == -1
        nodes = data_list.collect do |data|
          Node.new(data, @root, [])
        end
        @leafs += nodes
      else
        parent = @leafs[parent_ix]
        parent.data.alive = false
        @revive_nodes.push(parent)
        nodes = data_list.collect do |data|
          Node.new(data, parent, [])
        end
        parent.childern.replace(nodes)
        parent.data.results.replace([nil] * data_list.size)
        if parent.data.alive_childern == 0
          parent.data.alive_childern = data_list.size
        end
        @leafs += nodes
      end
    end

    def delete_leaf(leaf_ix)
      leaf = @leafs[leaf_ix]
      leaf.data.alive = false
      # only @root.parent is nil
      if !leaf.parent.parent.nil?
        if leaf.parent.data.alive_childern == -1
          leaf.parent.childern.each { |node| node.data.alive = false }
          leaf.parent.data.alive_childern = 0
          @leafs.push(leaf.parent)
          leaf.parent.childern.clear
        else
          leaf.parent.data.alive_childern -= 1
          if leaf.parent.data.alive_childern == 0
            @leafs.push(leaf.parent)
            leaf.parent.childern.clear
          end
        end
      end
    end

    def update
      no_update_flag = true
      dead_fiber_flag = false
      @leafs.each_with_index do |leaf, leaf_ix|
        @current, @current_ix = leaf, leaf_ix
        if !leaf.data.alive
          dead_fiber_flag ||= true
          next
        end
        # produce with condition
        condition = leaf.data.condition
        if condition.is_a?(Proc)
          next if !condition.call()
          # condition is a proc, fiber must not finish yet
          # run condition and resume if condition return true
          ret = leaf.data.fiber.resume
        else
          # condition is nil
          # the fiber might dead without return value
          # or just simple called: Fiber.yield
          ret = nil
          if leaf.data.args.nil?
            begin
              ret = leaf.data.fiber.resume
            rescue FiberError
              # fiber is terminated, delete leaf
              # the last results is nil, no need save to results
              dead_fiber_flag ||= true
              delete_leaf(leaf_ix)
              next
            end
          else
            # pass args when first resume fiber
            ret = leaf.data.fiber.resume(*leaf.data.args)
            # clear args
            leaf.data.args = nil
          end
        end
        no_update_flag &&= false
        # produce with result
        if ret.is_a?(Proc) || ret.nil?
          # condition can only be nil or lambda
          leaf.data.condition = ret
        else
          # only @root.parent is nil
          if !leaf.parent.parent.nil?
            # result is not nil or lambda,
            # the fiber should be terminated
            # save result in parent's results
            ix = leaf.parent.childern.find_index(leaf)
            leaf.parent.childern[ix] = nil
            leaf.parent.data.results[ix] = ret
          end
          dead_fiber_flag ||= true
          delete_leaf(leaf_ix)
        end
        # -------------------------------------------------
        # the yield block is used for Graphics.update,
        # when there's slow process, such as, lage data or heavy calculation
        # pass empty block or comment next line when there's too much fibers
        # -------------------------------------------------
        yield leaf, leaf_ix if block_given?
        @current = nil
      end
      if dead_fiber_flag
        @leafs.delete_if { |leaf| leaf.data.alive == false }
        @revive_nodes.each { |parent| parent.data.alive = true }
      end
      no_update_flag
    end

    def insert_fibers(fibers, root = false)
      data_list = fibers.collect { |f, args|
        Data.new(f, args, nil, true, 0, [])
      }
      insert_leafs(data_list, root ? -1 : @current_ix)
    end
  end

  @_block_fibers = []
  @_block_flag = false
  @fiber_tree = Fiber_Tree.new

  module_function

  def start
    @_block_fibers.clear
    @_block_flag = true
    yield
    @_block_flag = false
    @fiber_tree.insert_fibers(@_block_fibers, true)
    @_block_fibers.clear
  end

  def join
    @_block_fibers.clear
    @_block_flag = true
    yield
    @_block_flag = false
    @fiber_tree.insert_fibers(@_block_fibers)
    @_block_fibers.clear
    # yield out
    Fiber.yield
    # back and return results
    return @fiber_tree.current.data.results
  end

  def select(&block)
    @fiber_tree.current.data.alive_childern = -1
    join(&block)
  end

  def process(name, &block)
    define_singleton_method(name) do |*args|
      if @_block_flag
        f = Fiber.new(&block)
        @_block_fibers.push([f, args])
      else
        block.call(*args)
      end
    end
  end

  def update
    nil until @fiber_tree.update
  end
end
